class Solution(object):
    def climbStairs(self, n):
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            arr = [0, 1, 2]
            for i in range(3, n+1):
                arr.append(arr[-1] + arr[-2])
            return arr[-1]

if __name__ == '__main__':
    s = Solution()
    r = s.climbStairs(4)
    print(r)
